//dp[i][j]为以i位置开始，j位置结束的字串是否是一个回文串（0/1）
//如果 i == j dp[i][j] = 1
//如果 起始字符和结束字符相等 s[j] == s[i]
    //如果他们是两个相邻的字符 j - 1 == 1
    //或者他们中间的子串是一个回文串
    //那么i开头j结尾的子串也是一个回文串
class Solution {
public:
    string longestPalindrome(string s) {
        int n = s.size();
        vector<vector<bool>>dp (n, vector<bool>(n, false));
        string ret;

        for (int j = 0; j < n; j++)
        {
            for (int i = j; i >= 0; i--)
            {
                if (i == j)
                    dp[i][j] = true;
                else if (s[j] == s[i] && (j - i == 1 || dp[i + 1][j - 1] == 1))
                    dp[i][j] = true;
                
                if (dp[i][j])
                    ret = ret.size() > j - i + 1 ? ret : s.substr(i, j - i + 1);
            }
        }

        return ret;
       
    }
};